import java.util.*;

/**
* @description: 865. 具有所有最深节点的最小子树
* @author hewei
* @date 2022/9/9 16:18
* @version 1.0
*/

public class SubtreeWithAllDeepest {

    HashMap<Integer, List<TreeNode>> map = new HashMap<>();
    HashMap<TreeNode, TreeNode> parent = new HashMap<>();
    int max = 0;
    public TreeNode subtreeWithAllDeepest1(TreeNode root) {
        process(root, 0);
        List<TreeNode> list = map.get(max);
        Deque<TreeNode> queue = new LinkedList<>();
        queue.addAll(list);
        while (queue.size() != 1) {
            int size = queue.size();
            HashSet<TreeNode> set = new HashSet<>();
            while (size-- > 0) {
                TreeNode node = queue.poll();
                if (parent.containsKey(node) && !set.contains(parent.get(node))) {
                    queue.add(parent.get(node));
                    set.add(parent.get(node));
                }
            }
        }
        return queue.poll();
    }

    public void process(TreeNode node, int h) {
        max = Math.max(max, h);
        if (!map.containsKey(h)) map.put(h, new ArrayList<>());
        map.get(h).add(node);
        if (node.left != null) {
            parent.put(node.left, node);
            process(node.left, h + 1);
        }
        if (node.right != null) {
            parent.put(node.right, node);
            process(node.right, h + 1);
        }
    }

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        int l = depth(root.left);
        int r = depth(root.right);
        if (r == l) return root;
        if (r < l) return subtreeWithAllDeepest(root.left);
        return subtreeWithAllDeepest(root.right);
    }

    public int depth(TreeNode node) {
        if (node == null) return 0;
        return Math.max(depth(node.left), depth(node.right)) + 1;
    }
}